import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Solution882 {
    public int reachableNodes(int[][] edges, int maxMoves, int n) {
        int[] first=new int[n];
        Arrays.fill(first,-1);
        int[] next=new int[edges.length*2];
        int[] go=new int[edges.length*2];
        int[] should=new int[edges.length*2];
        int[] reach=new int[edges.length*2];
        int[] map=new int[edges.length*2];
        boolean[] b=new boolean[n];
        int cur=0;
        for (int[] edge : edges) {
            next[cur]=first[edge[0]];
            first[edge[0]]=cur;
            go[cur]=edge[1];
            should[cur]=edge[2];
            map[cur]=cur+1;
            cur++;
            next[cur]=first[edge[1]];
            first[edge[1]]=cur;
            go[cur]=edge[0];
            should[cur]=edge[2];
            map[cur]=cur-1;
            cur++;
        }
        int[] rest=new int[n];
        Arrays.fill(rest,-1);
        rest[0]=maxMoves;
        Queue<Integer> queue=new LinkedList<>();
        queue.offer(0);
        b[0]=true;
        while (!queue.isEmpty()){
            int t=queue.poll();
            b[t]=false;
            int v=first[t];
            while (v!=-1){
                if (rest[t]>=should[v]+1){
                    reach[v]=reach[map[v]]=should[v];
                    if (rest[t]-should[v]-1>=rest[go[v]]){
                        rest[go[v]]=rest[t]-should[v]-1;
                        if (!b[go[v]]){
                            b[go[v]]=true;
                            queue.offer(go[v]);
                        }
                    }
                }else {
                    reach[v]=Math.max(reach[v],rest[t]);
                    if (reach[v]+reach[map[v]]>=should[v]){
                        reach[v]=reach[map[v]]=should[v];
                    }
                }
                v=next[v];
            }
        }
        int ans=0;
        for (int i=0;i<n;i++){
            if (rest[i]>=0){
                ans++;
            }
        }
        for (int i=0;i<edges.length*2;i+=2){
            if (reach[i]==should[i]){
                ans=ans+reach[i];
            }else{
                ans=ans+reach[i]+reach[i+1];
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution882().reachableNodes(new int[][]{{0,1,10},{0,2,1},{1,2,2}},6,3));
    }
}
